package cn.guyouda.algorithms.sort;

public class MergeSort {


    public static void merge1(Comparable[] src, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;
        Comparable[] aux = new Comparable[100];

        for (int k = lo; k <= hi; k++) {
            aux[k] = src[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                src[k] = aux[j++];
            } else if (j > hi) {
                src[k] = aux[i++];
            } else if (less(aux[j], aux[i])) {
                src[k] = aux[j++];
            } else {
                src[k] = aux[i++];
            }
        }
    }


    //比较x是否小于y
    public static boolean less(Comparable x, Comparable y) {
        return x.compareTo(y) < 0;
    }

    //交换 x,y
    public static void exchange(Comparable[] src, int x, int y) {
        Comparable z = src[x];
        src[x] = src[y];
        src[y] = z;
    }


    public static void main(String[] args) {

        //测试数据
        String[] src = {"a", "x", "z", "i", "y", "o", "l", "q", "b", "d", "z", "s", "c"};
        Integer[] src1 = {100, 99, 70, 98, 99, 101, 3, 6, 676, 45, 25, 77, 80, 1, 0, 46, 28, 11111, 56666, 22, 6, 8, 29};

        System.out.println("===========原数组==========");
        for (String str : src) {
            System.out.print(str + ",");
        }

        merge1(src, 0, src.length / 2, src.length - 1);//排序

        System.out.println();
        System.out.println("==========排序后==========");
        for (String str : src) {
            System.out.print(str + ",");
        }


        System.out.println();
        System.out.println("==========原数组=========");
        for (int i = 0; i < src1.length; i++) {
            System.out.print(src1[i] + ",");
        }

        merge1(src1, 0, src1.length / 2, src1.length - 1);

        System.out.println();
        System.out.println("==========排序后==========");
        for (int i = 0; i < src1.length; i++) {
            System.out.print(src1[i] + ",");
        }

    }


}
